/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)  return l2;
        /*
        双指针法：同时操作两个指针，依次将l2中的节点按顺序插入l1中;
        1:当l2中节点大于等于l1中节点值时，根据l1中下一个节点值判断是否立即插入l1当前节点之后；
        2:当l2中节点小于l1中节点值时，根据l2中下一个节点值判断是否立即插入l1当前节点之前（当l1正好处于表头位置时例外）
        依据：两个链表均为已排序链表
        */
        ListNode* pL1 = l1;
        ListNode* pL2 = l2;
        //执行插入链表操作时暂存next指针
        ListNode* pL1Next = NULL;
        ListNode* pL2Next = NULL;
        //l1链表当前节点的前一个指针
        ListNode* pL1Prior = NULL;
        while(pL1 && pL2){
            if(pL2->val >= pL1->val){
                pL1Prior = pL1;
                if(pL1->next && (pL2->val > pL1->next->val)){
                    pL1 = pL1->next;
                    continue;
                }
                //将pL2插入pL1之后
                pL1Next = pL1->next;
                pL2Next = pL2->next;
                pL1->next = pL2;
                pL2->next = pL1Next;
                pL1 = pL2;
                pL2 = pL2Next;
            }else{
                //将pL2插入pL1之前
                if(pL1Prior){
                    pL1Prior->next = pL2;
                    pL1Prior = pL2;
                    if(pL2->next && pL2->next->val < pL1->val){
                        pL2 = pL2->next;
                        continue;
                    }
                    pL2Next = pL2->next;
                    pL2->next = pL1;
                    pL2 = pL2Next;
                }else{
                    pL1Prior = pL2;
                    pL2Next = pL2->next;
                    pL2->next = pL1;
                    pL2 = pL2Next;
                    //创建新表头
                    l1 = pL1Prior;
                }
            }
        }

        return l1;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)  return l2;
        else if(!l2)  return l1;
        /*
        递归法：需创建一个新链表来存储排序后的链表
        l1和l2当前节点进行比较，值小者即为当前合并链表的结点，然后值小者执行递增操作；
        由于每次合并链表后操作重复，可使用递归来实现，使代码更为简洁
        */
        ListNode* pMergedHead = NULL;
        if(l1->val < l2->val){
            pMergedHead = l1;
            pMergedHead->next = mergeTwoLists(l1->next, l2);
        }else{
            pMergedHead = l2;
            pMergedHead->next = mergeTwoLists(l1, l2->next);
        }
        return pMergedHead;
    }
};